Conventional content addressable memories (CAMs) can provide rapid matching between a specific pattern of received data bits, commonly known as a search key or comparand, and data values stored in a content addressable memory (CAM) array. In a CAM device, a CAM array can be searched in parallel. If a match occurs between each bit of a stored data value and a corresponding bit of an applied comparand, a match indication can be generated, via a match line, to indicate that the applied comparand is stored in the CAM. Data associated with the matching CAM location can then be returned. Thus, in a CAM device, a result can be determined from finding a matching value (content), and not from an address for a value, as is typically done for a random access memory (RAM).
Conventional CAM cells can include binary CAM cells as well as ternary CAM
A conventional binary CAM cell can store a data bit value (i.e., logic “0” or logic “1”). When such a stored data bit value matches an applied compare data bit value, the binary CAM cell can maintain a high impedance between a precharged match line, and a lower discharge potential. If all binary CAM cells connected to a given match line provide a match result, the match line can maintain the precharged state, indicating a match result. When a stored data bit value does not match an applied compare data bit value, the binary CAM cell can provide a low impedance between a precharged match line and lower discharge potential. Thus, if any one of the binary CAM cells connected to a given match line provides a no match result, the match line will be discharged, indicating a no match (miss) result for the comparand.
A conventional ternary CAM (TCAM) cell can store three states, including a logic “0”, logic “1” and a “don't care”. When such a TCAM cell stores a logic “0” or logic “1,”, the TCAM cell can provide the same essential match operation as a binary CAM cell. However, when such a TCAM cell stores a “don't care” value, the TCAM cell can provide a match result regardless of the compare data value applied to the TCAM cell.
In addition, to reduce the size of a TCAM system or device, it is often desirable to map mask to data entries in the form of a 1:N mapping. A mapping of 1:1 can identify a “full” TCAM. A mapping of 1:N, where N>1, can identify a pseudo-TCAM.
Among the numerous applications for memory systems using CAM devices or systems are network search engines (NSEs). NSEs can use TCAMs to provide fast searches of a database, list, or pattern. Binary CAMs can be used, for example, to implement media access control (MAC) tables, while TCAMs can be used to implement forwarding information base (FIB) and/or access control list (ACL) tables.
A schematic diagram of a conventional “X/Y” type TCAM cell is shown in FIG. 9. Referring to FIG. 9, a single conventional TCAM cell 900 generally includes a “stack” 902 and two static random access memory (SRAM) cells 904-0 and 904-1. In the particular arrangement of FIG. 9, SRAM cells (904-0 and 904-1) can store data bits (referred typically as an X-value and Y-value) to be compared by transistors within stack 902 against externally supplied comparand data provided at inputs CD and BCD. An input CD can provide a compare data value, while input BCD can provide a complementary compare data value (compare data “bar”). That is CD and BCD are complementary values with respect to each other. The stack 902 of FIG. 9 includes four N-type metal-oxide-semiconductor (MOS) transistors. Other conventional stacks can include six such transistors.
FIG. 9 shows an “X/Y” type TCAM cell. In such an arrangement, a masking value (don't care) is determined according to a data value stored in both SRAM cells (904-0 and 904-1). This is in contrast to a “V/M” type TCAM cell in which a masking value is determined according to one data value (e.g., M) stored in a single SRAM cell.
Conventional TCAM cells like that of FIG. 9 can suffer from a number of drawbacks. First, while such cells can be configured for binary operation (forcing the cell to a state other than don't care), such an approach can be wasteful, as two storage bits are dedicated to represents essentially one bit value. Further, conventional TCAM cells cannot be dynamically reconfigured in the field to be optimized for density depending upon a binary or ternary configuration. That is, to configure a conventional TCAM cell to operate as a binary CAM cell can require a write operation to one or both SRAM cells in such a circuit.
In light of the above, it would be desirable to arrive at a TCAM cell that can be dynamically reconfigurable between binary and ternary modes of operation. It would also be desirable for a device including such TCAM cells to support bit-wise maskable writes, as well as parallel mask writes to multiple location to emulate pseudo-ternary cell operations. Bit-wise maskable writes can be writes to multiple bit locations of a same column, as opposed to conventional row-wise writes. Still further, it is almost always desirable to arrive at circuit implementations that are compact relative to conventional approaches.